\subsection{Linear Programming}

Approaching the problem as an LP problem requires us to formulate it in terms of variables, an objective function and constraints on the variable values.

\subsubsection{Variables}

The solution to this problem answers all questions of the type: ``How many people
of type $T$ should be on duty in department $D$ at time slot $S$?'' To optimize the
solution, the LP-solver thus needs to consider $T \cdot D \cdot S$
variables ($x_{t,d,s}$). Since the solution needs to consider a quarter of a year,
this puts the number of time slots at $65 \cdot 24$, and thus the number of variables
will be in the tens of thousands, even for a small number of types and
departments. The values can be floats during the solving and subsequently rounded
to integers without much concern.

An alternative approach is to lock the sum of shifts at the known demand,
meaning all solutions must sum to exactly the number of shifts given in the
input. Using this approach we can ask the solution questions like: ``Which
department should man the shift of type $T$ at time slot $S$?'' This sets the number
of variables to the total number of shifts given in the input. However this
alternative approach considers categorical values and thereby makes it very
complicated if not impossible to express the constrains and objective functions
needed for an LP-solution.

\subsubsection{Objective Function}
The objective function could be expressed as a linear combination of the
variables. From a minimization approach the distances between the sums of shifts
in each department need to be minimized across weeks and quarters.

\begin{equation}
min: max(|\sum(X)_{dep}-\sum(X)_{total}|)
\label{eq:minmax}
\end{equation} 

This would make it expensive to have one department that has much more or much
less of the workload than the other departments. Expressing Eq. \ref{eq:minmax}
as a linear combination requires rewriting $max$, $abs$ and $sum$ functions as
linear combinations and combining them.


\subsubsection{Constraints}
The are few strict constrains on the distribution. But there is some upper
level on each variable representing the fact that the company can only employ a
limited number of call-center operators. Smaller preferences like ``Department 2
cannot work on July 4th'' can also be modelled as constrains.

\subsubsection{Conclusion}

It seems that it would be possible to solve the problem with a powerful
LP-solver. However the challenge of writing the cost-function and subsequently
running the solver on thousand of variables seems to exceed the scope of this
project and we will leave it to others to implement a working solution in LP.
